#include <iostream>
#include <vector>
struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode() : val(0), left(nullptr), right(nullptr) {}
      TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
      TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 };
using namespace std;

class Solution {
public:
// 从中序与后序遍历序列构造二叉树和从前序与中序遍历序列构造二叉树的区别就是
// 在前序与中序遍历序列构造二叉树是用前序来确定根而中序与后序遍历序列构造二叉树是后序确定根 
// 根是从后往前确定的还有区别的是在构造二叉树的时候因为后序的顺序是左右根 
// 所以在根--的时候前一个是右子树的根不是左子树的根所以在构造的时候先构造右树在构造左树
    TreeNode* _buildTree(vector<int>& inorder, vector<int>& postorder,int& posti,int instart,int inend)
    {
        TreeNode* root = new TreeNode(postorder[posti]);
        int rooti = 0;
        while(rooti<=inend)
        {
            if(inorder[rooti]==postorder[posti])
                break;
            else
                rooti++;
        }

        if(inend >= rooti+1)
        {
            root->right = _buildTree(inorder,postorder,--posti,rooti+1,inend);
        }
        else
        {
            root->right = nullptr;
        }
        if(instart <= rooti-1)
        {
            root->left = _buildTree(inorder,postorder,--posti,instart,rooti-1);
        }
        else
        {
            root->left = nullptr;
        }
        return root;

    }
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int posti = postorder.size()-1;
        int instart = 0;
        int inend = inorder.size()-1;
        TreeNode* head = _buildTree(inorder,postorder,posti,instart,inend);
        return head;
    }
};